import java.util.Arrays;

/**
 * 快速排序
 */
class FastSort {

    public static void main(String[] args) {
        //System.out.println(Arrays.toString(FastSort.ascSort(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})));
        System.out.println(Arrays.toString(FastSort.ascSort(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 8})));
        //System.out.println(Arrays.toString(FastSort.ascSort(new int[]{72, 6, 57, 88, 60, 42, 83, 73, 48, 85})));
    }

    /**
     * 从小到大排序
     *
     * @param nums
     * @return
     */
    public static int[] ascSort(int[] nums) {
        return sort(nums, 0, nums.length - 1);
    }

    /**
     * 使用第一个值作为基准，把比基准小的放在一边，把比基准大的放在一边
     * 递归下去
     * 复杂度n*log2n 因为每次循环需要处理n遍，一共处理log2n次
     *
     * @param nums
     * @param begin
     * @param end
     * @return
     */
    public static int[] sort(int[] nums, int begin, int end) {
        //记录基准
        int key = nums[begin];
        // 记录上一个替换的位置
        int last = begin;
        //记录方向
        boolean goRight = false;
        int left = begin, right = end;
        while (left <= right) {
            if (goRight) {
                if (nums[left] > key) {
                    //如果找到了比基准key大的
                    nums[last] = nums[left];
                    last = left;
                    goRight = false;
                }
                left++;
            } else {
                if (nums[right] < key) {
                    //如果找到了比基准key小的
                    nums[last] = nums[right];
                    last = right;
                    goRight = true;
                }
                right--;
            }
        }
        nums[last] = key;
        //递归
        if (last - begin > 1) {
            nums = sort(nums, begin, last - 1);
        }
        if (end - last > 1) {
            nums = sort(nums, last + 1, end);
        }
        return nums;
    }
}